package SearchAlgorithms;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

import Main.GenericSearchProblem;
import Maze.Maze;
import Tree.Node;
import Tree.Tree;

/**
 * 
 * Class GeneralSearch performs the search algorithms
 * 
 */
public class GeneralSearch {

	GenericSearchProblem problem;
	String strategy;
	Tree tree;
	LinkedList<Node> nodes = new LinkedList<Node>();
	PQsort pqs = new PQsort();
	PriorityQueue<Node> nodesH = new PriorityQueue<Node>(10000000, pqs);
	Expand expand;
	int countExpandedNodes = 0;
	int limit = 1;
	boolean visualize;

	/**
	 * The constructor generalSearch takes a search problem and a search
	 * strategy and whether or not to visualize
	 * 
	 * @param problem
	 * @param strategy
	 * @param visualize
	 * 
	 */
	public GeneralSearch(GenericSearchProblem problem, String strategy,
			boolean visualize) {
		this.strategy = strategy;
		this.problem = problem;
		this.visualize = visualize;
	}

	/**
	 * 
	 * First the initialState from the problem is added to the root node of the
	 * tree which is added to the queue. Then a loop is performed on the queue
	 * where it checks if the queue is empty , in which case there would be no
	 * solution and the method would terminate. Else it takes the first node in
	 * the queue and checks to see if it is the goal node, in which case it gets
	 * the path and returns it. Else according to the strategy a queuing
	 * function is called
	 * 
	 * @return The list of nodes leading to the goal from the root
	 * 
	 * 
	 */
	public LinkedList<Object> search() {

		Maze initMaze = (Maze) problem.getInitialstate();
		Node initNode = new Node(true, null, 0, null, initMaze);
		nodes.add(initNode);
		nodesH.offer(initNode);
		tree = new Tree(initNode);

		while (true) {
			Node currentNode;
			if (nodes.isEmpty()) {
				System.out.println("lost");
				LinkedList<Object> output = new LinkedList<Object>();

				output.add("No solution");
				output.add("Infinity");
				output.add(countExpandedNodes);
				return output;
			}
			if (strategy.equalsIgnoreCase("GR1")
					|| strategy.equalsIgnoreCase("GR2")
					|| strategy.equalsIgnoreCase("AS1")
					|| strategy.equalsIgnoreCase("AS2")) {

				if (nodesH.isEmpty()) {
					LinkedList<Object> output = new LinkedList<Object>();

					output.add("No solution");
					output.add("Infinity");
					output.add(countExpandedNodes);
					return output;
				} else {
					currentNode = nodesH.poll();
				}

			} else {
				currentNode = nodes.removeFirst();
			}
			if (visualize) {
				System.out.println("Current maze expaned");
				Maze mazeToPrint = (Maze) currentNode.getState();
				for (int i = 0; i < 6; i++) {
					for (int j = 0; j < 6; j++) {

						System.out.print(mazeToPrint.getGrid()[j][i]);
					}
					System.out.println();
				}
				System.out.println();
				System.out.println();
			}
			if ((problem.getGoalTest()).goalTest(currentNode)) {

				LinkedList<Node> path = new LinkedList<Node>();
				LinkedList<Object> output = new LinkedList<Object>();
				while (currentNode != null) {
					path.addFirst(currentNode);
					currentNode = (Node) currentNode.getParentNode();
				}

				int cost = path.size() - 1;

				output.add(path);
				output.add(cost);
				output.add(countExpandedNodes);

				return output;
			}

			switch (strategy) {
			case "BF":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						visualize);
				nodes = Breadth1stSearch();
				break;
			case "DF":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						visualize);
				nodes = Depth1stSearch();
				break;
			case "ID":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						visualize);
				nodes = IterativeDeepeningSearch();
				break;
			case "GR1":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						1, visualize);
				GreedySearch();
				break;
			case "GR2":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						2, visualize);
				GreedySearch();
				break;
			case "AS1":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						3, visualize);
				AStarSearch();
				break;
			case "AS2":
				expand = new Expand(currentNode, problem.getOperators(), tree,
						4, visualize);
				AStarSearch();
				break;
			default:
				return null;
			}
		}

	}

	/**
	 * This method takes the first element of the queue and expands it and adds
	 * all children of the node to the end of the list
	 * 
	 * @return the queue of all nodes
	 */
	public LinkedList<Node> Breadth1stSearch() {
		countExpandedNodes++;
		LinkedList<Node> children = expand.expandNode();
		nodes.addAll((LinkedList<Node>) children);
		expand = null;
		return nodes;

	}

	/**
	 * This method takes the first element of the queue and expands it and adds
	 * all children of the node to the beginning of the list
	 * 
	 * @return the queue of all nodes
	 */
	public LinkedList<Node> Depth1stSearch() {
		countExpandedNodes++;
		LinkedList<Node> children = expand.expandNode();
		nodes.addAll(0, (LinkedList<Node>) children);
		expand = null;
		return nodes;

	}

	/**
	 * This method expands the first element of the queue and adds the children
	 * to the queue only if their depth is less than or equal to the limit. The
	 * search of the tree starts with depth = 0 reaching infinity
	 * 
	 * @return the queue of all nodes
	 */
	public LinkedList<Node> IterativeDeepeningSearch() {

		countExpandedNodes++;
		LinkedList<Node> children;
		LinkedList<Node> addedChildren = new LinkedList<Node>();

		children = expand.expandNode();

		for (Node node : children) {

			if (node.getDepth() <= limit) {
				if (!addedChildren.contains(node)) {
					addedChildren.add(node);
				}
			}
		}

		nodes.addAll(0, (LinkedList<Node>) addedChildren);
		limit++;

		return nodes;
	}

	/**
	 * This method takes the first element of the queue and expands it and calls
	 * the method BestFirstSearch for each child node
	 */
	public void GreedySearch() {
		countExpandedNodes++;
		LinkedList<Node> children = expand.expandNode();
		for (Node node : children) {
			int h = node.getHeuristic();
			BestFirstSearch(node, h);
		}

	}

	/**
	 * 
	 * The method adds the node to the priority queue according to the heuristic
	 * 
	 * @param node
	 *            to be added to priority queue
	 * @param f
	 *            which is the value of the heuristic of the node
	 * @return
	 */
	public PriorityQueue<Node> BestFirstSearch(Node node, int f) {

		nodesH.offer(node);
		return nodesH;
	}

	/**
	 * This method takes the first element of the queue and expands it and calls
	 * the method BestFirstSearch for each child node
	 */
	public void AStarSearch() {
		countExpandedNodes++;
		LinkedList<Node> children = expand.expandNode();
		for (Node node : children) {
			int f = node.getHeuristic();
			BestFirstSearch(node, f);
		}
	}

}

/**
 * 
 * The PQSort class implemets the comparator which compares the nodes before
 * adding them to the queue
 */
class PQsort implements Comparator<Node> {

	public int compare(Node one, Node two) {
		return one.getHeuristic() - two.getHeuristic();
	}
}
